package hot100;

import org.junit.Test;

public class NumSquares {
    public int numSquares(int n) {
        //完全背包
        int[] dp = new int[n + 1];
        dp[0] = 0;
        for (int i = 1; i < dp.length; i++) {
            dp[i] = Integer.MAX_VALUE;
        }
        //平方数数组
        int[] square = new int[101];
        //初始化
        for (int i = 0; i < square.length; i++) {
            square[i] = i * i;
        }
        //完全背包去取
        for (int i = 1; i < square.length; i++) {
            for (int j = square[i]; j < dp.length; j++) {
                dp[j] = Math.min(dp[j],dp[j - square[i]] + 1);
            }
        }

        return dp[n];
    }

    @Test
    public void test() {
        String s = "曹思远";
        char[] chars = s.toCharArray();
        for (char aChar : chars) {
            System.out.println(aChar);
        }
    }
}
